package com.cg.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * 739.每日温度
 *
 * @program: LeetCode->LeetCode_739
 * @description: 739.每日温度
 * @author: cg
 * @create: 2021-09-07 19:12
 **/
public class LeetCode_739 {

    @Test
    public void test739() {
        System.out.println(Arrays.toString(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
    }

    /**
     * 请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * <p>
     * 示例 1:
     * 输入: temperatures = [73,74,75,71,69,72,76,73]
     * 输出: [1,1,4,2,1,1,0,0]
     * <p>
     * 示例 2:
     * 输入: temperatures = [30,40,50,60]
     * 输出: [1,1,1,0]
     * <p>
     * 示例 3:
     * 输入: temperatures = [30,60,90]
     * 输出: [1,1,0]
     * <p>
     * 提示：
     * 1) 1 <= temperatures.length <= 105
     * 2) 30 <= temperatures[i] <= 100
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < temperatures.length; i++) {
            int temperature = temperatures[i];
            while (!deque.isEmpty()&&temperature>temperatures[deque.peek()]) {
                Integer per = deque.pop();
                result[per] = i-per;
            }
            deque.push(i);
        }
        return result;
    }
}
